\section{Problema 2: Profesores visitantes}

\subsection{Introducción}
El Departamento de Computación de la FCEyN extendió una invitación a un grupo de
profesores extranjeros para realizar un ciclo de cursos. Cada profesor estipuló una
fecha factible para venir a dar el curso y las fechas son inamovibles. 

El problema consiste en escribir un algoritmo de manera tal que, dadas las fechas 
ofrecidas por los profesores (fecha inicio y fecha fin), indique qué cursos 
deberían elegirse para maximizar la cantidad de cursos en el ciclo, de manera que no 
se solapen.

Por ejemplo:
\begin{verbatim}
INPUT: 6 1 3 1 6 4 8 2 5 5 10 9 10 | OUTPUT: 1 3 6
\end{verbatim}
ya que los cursos a dictar son [1,3],[4,8],[9,10].

\subsection{Desarrollo}

La soluci\'on planteada para este problema consiste en ordenar dentro de una lista todos los cursos según su fecha de finalización. Es decir, que sin importar cu\'al sea la fecha de inicio del curso, si un curso 'A' se encuentra primero que otro curso 'B' dentro de la lista ordenada de cursos, podemos garantizar que la fecha de finalizaci\'on de 'A' es anterior a la fecha de finalizaci\'on de 'B'.

Adem\'as, utilizaremos una variable que denominamos \textsl{ultima\_fecha} para chequear qu\'e curso podemos seleccionar de la lista sin que se solape con ninguno de los que ya elegimos.

El m\'etodo para maximizar la cantidad de cursos seleccionados sin que estos se solapen entre s\'i consiste en recorrer la lista de cursos ordenada elemento por elemento.

Para cada elemento que seleccionamos chequeamos si su fecha de inicio es anterior a \textsl{ultima\_fecha}. Si lo es, quiere decir que el curso se solapa con alguno que ya seleccionamos y no sirve. Si no, agregamos ese curso a la lista \textsl{resultado} y cambiamos \textsl{ultima\_fecha} por la fecha de finalizaci\'on del curso que acabamos de seleccionar.

Finalmente, devolvemos como resultado los cursos que agregamos en \textsl{resultado}.

\subsubsection{Correctitud}

Para demostrar que nuestro algoritmo funciona es necesario demostrar que si ordenamos el arreglo de cursos seg\'un su fecha de finalizaci\'on existe un m\'etodo para maximizar la cantidad de cursos seleccionados, sin que ninguno se solape y recorriendo el arreglo una sola vez. En particular, nos referimos al m\'etodo mencionado en la secci\'on de arriba.

Supongamos que tenemos un determinado arreglo de cursos. Queremos demostrar que si ordenamos ese arreglo de cursos seg\'un la fecha de finalizaci\'on de menor a mayor entonces alcanza con tomar el primer curso y descartar todos los que se solapen con este y as\'i continuar tomando el primer curso y descartando los que se solapen.

\begin{center}
    \includegraphics[scale=0.6]{./img/Grupos_cursos.jpg} \\
     \small{\textbf{Figura 3}: Posible instancia del problema}
    \label{fig:fig3}
\end{center}

Para demostrar que nuestro m\'etodo maximiza la cantidad de cursos seleccionados sin que \'estos se solapen entre s\'i tomamos una lista de cursos aleatoria y la ordenamos seg\'un la fecha de finalizaci\'on. Luego vamos a dividir los cursos ya ordenados en grupos. Cada grupo toma al primer curso siguiendo el orden de la lista que no est\'e a\'un en ning\'un grupo y a todos los cursos siguientes que se solapen con este. Es decir, incluye a todos los cursos siguientes cuya fecha de inicio sea anterior a la fecha de finalizaci\'on del primer curso. Notar que el primer elemento de cada grupo coincide con el curso que selecciona nuestro algoritmo, y que el resto de los cursos dentro de cada grupo coinciden con los que el algoritmo descarta. Por otro lado, el primer elemento del grupo siguiente va a ser el primer curso que tenga su fecha de inicio posterior a la fecha de finalizaci\'on del primer elemento del grupo actual.

Como para armar cada grupo elegimos los cursos en orden dentro de una lista que estaba ordenada de menor a mayor seg\'un la fecha de finalizaci\'on del curso, podemos garantizar que todos los elementos del grupo tienen fecha de finalizaci\'on mayor o igual a la fecha de finalizaci\'on del primer elemento del grupo (desde ahora \textsl{ultima\_fecha}). Como adem\'as armamos cada grupo eligiendo los elementos que tienen fecha de inicio anterior a \textsl{ultima\_fecha}, podemos garantizar tambi\'en que dentro de cada grupo el valor \textsl{ultima\_fecha} se encuentra despu\'es que la fecha de inicio de todos los cursos del grupo y antes que la fecha de finalizaci\'on. Es decir, es una fecha 'comun' a todos los cursos. Los cursos, por lo tanto, se solapan, lo que prueba que los grupos est\'an compuestos de elementos que son mutuamente excluyentes entre s\'i

Por otro lado, queremos probar que ning\'un curso queda afuera de alguno de los grupos de elementos mutuamente excluyentes. Para esto, basta probar que no queda afuera ning\'un curso que estuviera antes que el primer grupo, despu\'es del \'ultimo, o entre medio de dos grupos.

Supongamos que existe un curso que est\'a antes que el primer elemento del primer grupo que armamos. Como todav\'ia no armamos ning\'un grupo, la fecha de finalizaci\'on del \'ultimo curso seleccionado es 0 (porque a\'un no seleccionamos ninguno). Pero esto es absurdo, porque si la fecha de inicio del curso que nos qued\'o afuera es mayor a 0 (cosa que sucede siempre porque la fecha es un entero positivo distinto de 0) entonces lo hubi\'eramos seleccionado y por ende, formar\'ia parte de un grupo. Supongamos ahora que hay un curso que se no tiene grupo y se encuentra, en la secuencia ordenada, con posterioridad a otro que s\'i tiene grupo. Llamemos 'N' al primer curso del \'ultimo grupo que armamos en nuestra secuencia y 'A' al curso que qued\'o sin grupo. Entonces hay dos posibilidades. La primera es que la fecha de inicio de A sea posterior o igual a la fecha de finalizaci\'on de N. Pero esto es absurdo, porque si fuera as\'i A hubiera sido seleccionado para ser el primer elemento de un grupo nuevo. La 
segunda es que la fecha de inicio de A sea anterior a la fecha de finalizaci\'on de N. Pero esto tambi\'en es absurdo porque entonces A deber\'ia pertenecer al mismo grupo que N. Podemos afirmar entonces que todos los cursos de cualquier instancia pertenecen a alg\'un grupo.

Queremos demostrar ahora que dada cualquier instancia posible del problema (cualquier conjunto de cursos existente), la m\'axima cantidad de cursos que podemos elegir sin que se solapen entre s\'i es igual a la cantidad de grupos de elementos mutuamente excluyentes que podemos armar sin dejar afuera ning\'un elemento.

Supongamos que tengo una selecci\'on de cursos que es soluci\'on de una instancia dada y que tiene m\'as cantidad de elementos que la cantidad de grupos con elementos mutuamente excluyentes que puedo armar para esa instancia sin dejar ning\'un  elemento afuera. Pero entonces, deber\'ia existir alg \'un grupo que tuviera m\'as de un curso seleccionado. Esto es absurdo, ya que contradice que los grupos est\'en conformados de elementos mutuamente excluyentes para nuestra selecci\'on.

Dado que nuestro algoritmo selecciona un elemento por cada grupo mutuamente excluyente que podemos armar sin dejar ning\'un elemento afuera, podemos afirmar que nuestra soluci\'on forma parte del conjunto de soluciones \'optimas, ya que no hay ninguna otra soluci\'on posible que seleccione una mayor cantidad de cursos sin que dos cursos de nuestra seleccion se solapen entre s\'i.


\subsection{Análisis de complejidad}

\begin{algorithm}
%        \DontPrintSemicolon
        \SetKwInOut{Input}{input}
        \SetKwInOut{Output}{output}
        \SetKwComment{Complejidad}{\color{Blue}$\rhd$ $\mathcal O($}{\color{Blue}$\mathcal )$}
        \SetKwComment{SubComplejidad}{\color{Red}$\square$ $\mathcal O($}{\color{Red}$\mathcal )$}
        \SetKwComment{SubSubComplejidad}{\color{Fuchsia}$\fullmoon$ $\mathcal O($}{\color{Fuchsia}$\mathcal )$}
        \SetKwComment{ComplejidadTotal}{\color{Blue}Complejidad total $\rhd$ $\mathcal O($}{\color{Blue}$\mathcal )$}
        \SetKwComment{SubComplejidadTotal}{\color{Red}Complejidad total $\square$ $\mathcal O($}{\color{Red}$\mathcal )$}
        \SetKwComment{SubSubComplejidadTotal}{\color{Fuchsia}Complejidad total $\fullmoon$ $\mathcal O($}{\color{Fuchsia}$\mathcal )$}

%       \SetKwData{S}{S}
        \SetKwData{A}{A}
        \SetKwData{n}{n}
%~ 
        \Input{Vector de tuplas de enteros \textbf{cursos} donde cada tupla tiene los valores \texttt{fecha\_de\_inicio\_del\_curso} y \texttt{fecha\_de\_finalizaci\'on}}
        \Output{Un vector de tuplas \texttt{soluci\'on} tal que:
	     \begin{itemize}
	     \item Todos los elementos de 'soluci\'on' est\'an contenidos en 'cursos'
	     \item No hay ning\'un valor tal que ese valor est\'e contenido entre la fecha de inicio y la fecha de finalizaci\'on de una tupla y de otra distinta (es decir, no hay dos cursos que se solapen).
	     \item No hay ning\'un otro vector 'P' que cumpla las dos condiciones anteriores y tenga m\'as elementos que 'soluci\'on'
	    \end{itemize}
        }
        \BlankLine
        crear un heap a partir del vector \texttt{cursos} tomando como par\'ametro de comparaci\'on la variable fecha\_de\_finalizaci\'on \Complejidad*[r]{\color{blue}$n$}
        asigno a la variable $ultima\_fecha$ el valor 0 \Complejidad*[r]{\color{blue}$1$}
        \For(\Complejidad*[f]{\color{Blue}$n$}){$cursos\_i$ con $[$ i $|$ $0 ... n$ $)$}{
			\If(\Complejidad*[f]{\color{Blue}$1$}){el inicio de $cursos\_i$ es antes de la $ultima\_fecha$}{
    	    descartamos $cursos\_i$ \Complejidad*[r]{\color{blue}$log(n)$}
			\Else{
				actualizamos $ultima\_fecha$ con $fecha_de_finalizacion$ de $cursos\_i$ \Complejidad*[r]{\color{blue}$1$}
				agregamos $cursos\_i$ al vector \texttt{solucion} \Complejidad*[r]{\color{blue}$1$}
				descartamos $cursos\_i$ \Complejidad*[r]{\color{blue}$log(n)$}}}}

        \caption{Ejercicio 2 - Complejidad}
    \end{algorithm}

La complejidad total del algoritmo resulta ser:

\begin{center}
$5 \cdot O(1) + O(n) + O(log(n)) \subset O(n \cdot log(n))$
\end{center}

\subsection{Análisis de casos}
Como primer caso a analizar, consideramos la instancia donde no hay ningún curso disponible. En dicho caso el algoritmo devuelve cero.

\begin{verbatim}
>> INPUT: 0 | OUTPUT: 0
\end{verbatim}

También podemos observar el caso donde todos los cursos ingresados se solapan entre sí. En este caso, la aplicación devolverá que solo es posible realizar un curso de todos los disponibles. El curso elegido será el que tenga la menor fecha de finalización.

\begin{verbatim}
>> INPUT: 5 2 10 1 5 3 7 3 10 4 6 | OUTPUT: 1 1 5
\end{verbatim}

En contrapartida, veremos el caso en el cual ningún curso se solapa. De esta manera, los cursos a los que uno puede asistir serán todos los disponibles.

\begin{verbatim}
>> INPUT: 5 2 5 10 13 7 9 17 28 14 16 | OUTPUT: 5 2 5 7 9 10 13 14 16 17 28
\end{verbatim}

Finalmente, tenemos el caso promedio, donde las instancias seguirán un comportamiento pseudo-aleatorio. Como ejemplo, usaremos la siguiente instancia, creada con el generador de instancias para el presente problema. El mismo permite crear intervalos de fechas principio y fin para cierta cantidad $n$ de cursos, los cuales seguirán una distribución uniforme o gaussiana (según se le indique por argumento).

\begin{verbatim}
>> INPUT: 5 30 31 17 31 22 31 20 22 14 18 | OUTPUT: 3 14 18 20 22 30 31
\end{verbatim}

\subsection{Test de performance}

Conociendo la complejidad de nuestro algoritmo, observemos su comportamiento en la práctica ejecutando varios casos de prueba, algunos de los cuales serán los que analizamos previamente sus resultados. Detallemos cada uno de ellos:

\begin{itemize}
	\item Distribución uniforme: los cursos son construídos con números pseudo-aleatorios generados por algoritmos de la STL que siguen una distribución uniforme.
	\item Distribución gaussiana: los cursos son construídos con números pseudo-aleatorios generados por algoritmos de la STL que siguen una distribución normal.
		\begin{itemize}
			\item a) la mediana vale 125.
			\item b) la mediana vale 250.
			\item c) la mediana vale 375.
		\end{itemize}
	\item Todos solapados: todos los cursos se solapan entre sí (un intervalo de tiempo es compartido por todos los cursos). La distribución usada es la uniforme.
	\item Ninguno solapado: la intersección para todo curso de la instancia con cualquier otro curso restante, es vacía. La distribución usada es la uniforme.
\end{itemize}

Todos los datos resultantes son reflejados en el mismo gráfico, el cual se presenta a continuación:

\begin{center}
    \includegraphics[scale=0.7]{./img/compSolapamiento1.png} \\
     \small{\textbf{Figura 4}: 500 instancias, con 100 iteraciones por cada una}
    \label{fig:fig4}
\end{center}

Como habíamos concluído, todos los casos cumplen en la práctica con la complejidad indicada. De hecho los tiempos consumidos son muy similares entre sí. De este hecho observamos que los tiempos de ejecución no se ven demasiado afectados por las distribuciones que siguen los cursos. Empíricamente es indiferente si hay mas solapamiento de cursos alrededor de algún valor, ya que de todos modos el algoritmo debe recorrer todos y cada uno de los cursos en cuestión y hacer las comparaciones pertinentes. Además, en todos los casos se descarta el curso actual del vector original, por lo tanto eso se verá reflejado en todos los casos. La única diferencia real entre todos los casos es la cantidad de veces que se agrega un curso al vector solución. A mas elementos agregados a dicho vector, mayor será la complejidad final real. Éste es el motivo por el cual el caso que mas tiempo de ejecución posee es en el cual ningún curso se solapa, ya que al no haber solapamiento, todos los elementos serán agregados a la solución. 
Por ende, el vector solución de la instancia será una permutación del vector indicado en la entrada.

\subsection{Compilar y ejecutar}

El archivo donde se encuentra la resolución del problema se encuentra en \texttt{pro2/src/main.cpp}. Para compilarlo hay que llamar a \texttt{make} en una terminal. Una vez hecho esto, se lo puede ejecutar mediante \texttt{./pro2 < \hspace{1bp} nombre\_input.txt}, donde \texttt{nombre\_input.txt} es el archivo con las instancias del problema.
Luego de hacer las acciones pertinentes, la aplicación devolverá por pantalla la máxima cantidad de cursos a los que se puede inscribir un alumno para poder cursarlos sin que los mismos se solapen. Además se indican cuales son los cursos elegidos para obtener dicho resultado.

También se puede correr el test de performance, ejecutando \texttt{make test\_performance} (en el path \texttt{pro2/etc/}). Luego lo ejecutamos escribiendo \texttt{./test\_performance < \hspace{1bp} input.txt}, donde \texttt{input.txt} representa el archivo donde están escritas las instancias a resolver. En el comienzo del fichero se debe escribir en una nueva línea, la cantidad de iteraciones a realizar. Los resultados se guardarán en un nuevo fichero creado automáticamente llamado \texttt{res\_performance.txt} (cantidad de cursos totales en la instancia resuelta y cantidad de tiempo requerido en promedio, según las iteraciones ingresadas como parámetro, para resolver dicha instancia).

Con \texttt{make generador} (también en el path \texttt{pro2/etc/}), podemos compilar el programa que genera el archivo con instancias pseudo-aleatorias. Para ejecutarlo, debemos escribir \texttt{./generador output.txt dist cant inicio fin}, donde \texttt{output.txt} sería el fichero donde se guardarán las instancias generadas, \texttt{dist} es un entero del 1 al 4 (``1'' para elegir una distribución gaussiana, ``2'' para una distribución uniforme, ``3'' para generar casos donde todos los cursos se solapen y ``4'' para crear instancias donde ningún curso se solape), \texttt{cant} sería la cantidad de instancias a generar (sea $n$ el valor ingresado, se crearán $n$ instancias, una para cada $i$ entre 1 y $n$) y los valores \texttt{inicio} y \texttt{fin} son dos enteros que indicamos como fechas límite para la elección aleatoria de cursos.
